package com.example.leetcode.trainingcamp.week9.sunday;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
 *
 * 示例：
 *
 * 输入：
 * [
 *   [0,2,1,0],
 *   [0,1,0,1],
 *   [1,1,0,1],
 *   [0,1,0,1]
 * ]
 * 输出： [1,2,4]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/pond-sizes-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Offer16_19 {

    private final List<Integer> result = new ArrayList<>();
    private boolean[][] visit ;
    private int sum = 0;
    private int len;
    private int len1;

    public int[] pondSizes(int[][] land) {
        len = land.length;
        len1 = land[0].length;
        visit = new boolean[len][len1];
        int[][] t = {{0,-1},{0,1},{1,0},{-1,-0},{1,1},{1,-1},{-1,-1},{-1,1}};
        for (int i =0;i<len;i++) {
            for (int j =0;j<len1;j++){
                if (!visit[i][j] && land[i][j] ==0) {
                    sum = 0;
                    dfs(land,t,i,j);
                    result.add(sum);
                }
            }
        }
        int[] r = new int[result.size()];
        for (int i =0;i<result.size();i++){
            r[i] = result.get(i);
        }
        Arrays.sort(r);
        return r;
    }

    public void dfs(int[][] land,int[][]t,int row ,int col){
        if (land[row][col] != 0) return;
        if (!visit[row][col]){
            sum++;
            visit[row][col] = true;
            for (int[]t1:t) {
                int r = row + t1[0];
                int c = col + t1[1];
                if (r>=0 && r<len && c>= 0 && c<len1 &&!visit[r][c]){
                    if (land[r][c] == 0){
                        dfs(land,t,r,c);
                    }
                }
            }
        }
    }
}


class TestOffer16_19{
    public static void main(String[] args) {
        int[][] land = {{0,2,1,0},{0,1,0,1},{1,1,0,1},{0,1,0,1}};
        Offer16_19 o = new Offer16_19();
        int[] ints = o.pondSizes(land);
        for (int i:ints) System.out.println(i+" ");
    }
}